Search Results

Documents authored by Tan, Jane


Document
On Comparable Box Dimension

Authors: Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.

Cite as

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten},
  title =	{{On Comparable Box Dimension}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38},
  URN =		{urn:nbn:de:0030-drops-160461},
  doi =		{10.4230/LIPIcs.SoCG.2022.38},
  annote =	{Keywords: geometric graphs, minor-closed graph classes, treewidth fragility}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail